package com.hr.leetcode.动态规划;

/**
 * @author 周恒哲
 * @date 2020/06/02
 * <p>
 * 第 1 步：状态设计（特别重要）
 * dp[i][j]：以 nums[i] 结尾的连续子数组的最值，计算最大值还是最小值由 j 来表示，j 就两个值；
 * 当 j = 0 的时候，表示计算的是最小值；
 * 当 j = 1 的时候，表示计算的是最大值。
 * 这样一来，状态转移方程就容易写出。
 * <p>
 * 第 2 步：推导状态转移方程（特别重要）
 * 由于状态的设计 nums[i] 必须被选取（请大家体会这一点，这一点恰恰好也是使得子数组、子序列问题更加简单的原因：当情况复杂、分类讨论比较多的时候，需要固定一些量，以简化计算）；
 * <p>
 * nums[i] 的正负和之前的状态值（正负）就产生了联系，由此关系写出状态转移方程：
 * <p>
 * 当 nums[i] > 0 时，由于是乘积关系：
 * 最大值乘以正数依然是最大值；
 * 最小值乘以同一个正数依然是最小值；
 * 当 nums[i] < 0 时，依然是由于乘积关系：
 * 最大值乘以负数变成了最小值；
 * 最小值乘以同一个负数变成最大值；
 * 当 nums[i] = 0 的时候，由于 nums[i] 必须被选取，最大值和最小值都变成 00 ，合并到上面任意一种情况均成立。
 * 但是，还要注意一点，之前状态值的正负也要考虑：例如，在考虑最大值的时候，当 nums[i] > 0 是，如果 dp[i - 1][1] < 0 （之前的状态最大值） ，此时 nums[i] 可以另起炉灶（这里依然是第 53 题的思想），此时 dp[i][1] = nums[i] ，合起来写就是：
 * <p>
 * <p>
 * dp[i][1] = max(nums[i], nums[i] * dp[i - 1][1]) if nums[i] >= 0
 * 其它三种情况可以类似写出，状态转移方程如下：
 * <p>
 * <p>
 * dp[i][0] = min(nums[i], nums[i] * dp[i - 1][0]) if nums[i] >= 0
 * dp[i][1] = max(nums[i], nums[i] * dp[i - 1][1]) if nums[i] >= 0
 * <p>
 * dp[i][0] = min(nums[i], nums[i] * dp[i - 1][1]) if nums[i] < 0
 * dp[i][1] = max(nums[i], nums[i] * dp[i - 1][0]) if nums[i] < 0
 * 第 3 步：考虑初始化
 * 由于 nums[i] 必须被选取，那么 dp[i][0] = nums[0]，dp[i][1] = nums[0]。
 * <p>
 * 第 4 步：考虑输出
 * 题目问连续子数组的乘积最大值，这些值需要遍历 dp[i][1] 获得。
 **/
public class _152_乘积最大子数组 {

    public static int maxProduct(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        // dp[i][0]：以 nums[i] 结尾的连续子数组的最小值
        // dp[i][1]：以 nums[i] 结尾的连续子数组的最大值
        int[][] dp = new int[len][2];
        dp[0][0] = nums[0];
        dp[0][1] = nums[0];
        for (int i = 1; i < len; i++) {
            if (nums[i] >= 0) {
                dp[i][0] = Math.min(nums[i], nums[i] * dp[i - 1][0]);
                dp[i][1] = Math.max(nums[i], nums[i] * dp[i - 1][1]);
            } else {
                dp[i][0] = Math.min(nums[i], nums[i] * dp[i - 1][1]);
                dp[i][1] = Math.max(nums[i], nums[i] * dp[i - 1][0]);
            }
        }
        int res = dp[0][1];
        for (int i = 1; i < len; i++) {
            res = Math.max(res, dp[i][1]);
        }
        return res;
    }

    public int maxProduct2(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }

        int preMax = nums[0];
        int preMin = nums[0];

        // 滚动变量
        int curMax;
        int curMin;

        int res = nums[0];
        for (int i = 1; i < len; i++) {
            if (nums[i] >= 0) {
                curMax = Math.max(preMax * nums[i], nums[i]);
                curMin = Math.min(preMin * nums[i], nums[i]);
            } else {
                curMax = Math.max(preMin * nums[i], nums[i]);
                curMin = Math.min(preMax * nums[i], nums[i]);
            }
            res = Math.max(res, curMax);

            // 赋值滚动变量
            preMax = curMax;
            preMin = curMin;
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(_152_乘积最大子数组.maxProduct(new int[]{
                2, 3, -2, 4
        }));
    }
}
